\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, inner=2cm, outer=3cm, top=2cm,
bottom=3cm, bindingoffset=1cm]{geometry}

\title{\textbf{Implementaci\'{o}n del Algoritmo de Edmonds-Karp en Python}}

\author{
Fabre, Facundo \and
		Quiroga, Lautaro\and
		Silvi, Luciano\and
		Teruel, Milagro\and
		Torti López, Ezequiel}
\date{4 de Junio de 2012}
\begin{document}

\maketitle

\section{Introducción}

En este proyecto, implementaremos el algoritmo de Edmonds-Karp, que permite hallar un flujo maximal en una network, con complejidad  O(V E^2). 
Para llevar a cabo esta implementación, partimos de la especificación dada por la cátedra.


\section{Modularización}
Contamos con dos módulos principales que siguen los lineamientos dados por la cátedra:
\begin{itemize}
\item apy.py
\item main.py
\end{itemize}
El módulo api.py provee la clase \texttt{EstadoEK} e incluye internamente a otros módulos:
\begin{itemize}
\item \texttt{Camino.py}: Provee la clase \texttt{Camino\_aumentante} y los métodos para operar sobre éste, ellos son:
\begin{itemize}
\item \texttt{add(x)}: agrega un elemento a la cola de la cual se extrae luego un camino;
\item \texttt{esta\_en\_cola(x)}: evuelve un booleano indicando si un elemento particular está en la cola; 
\item \texttt{elemento()}: evuelve el elemento que estamos revisando en determinado momento;
\item \texttt{ancestro(x)}: devuelve el ancestro de un elemento;
\item \texttt{camino\_vacio()}: devuelve un booleano indicando si ya hemos revisado toda la cola.
\end{itemize}
\item \texttt{Flujo.py}: Provee la clase \texttt{Flujo} y los métodos para operar sobre éste:
\begin{itemize}
\item \texttt{capSobrante(x,y)}: devuelve la capacidad sobrante del lado xy;
\item \texttt{aumentar(camino)}: aumenta el flujo sobre un camino dado, actualizando el flujo maximal;
\item \texttt{flujo\_maximal()}: devuelve el valor del flujo maximal.
\end{itemize}
\end{itemize}
El módulo main.py sólo realiza llamadas a funciones de la api, desconociendo como ésta está implementada internamente.
La modularización de la api se realizó de este modo porque nos permite separar conceptos (flujos, caminos) y escribir código más legible, facilitando tareas de debugging.
\section{Tests}
Para testear el correcto funcionamiento del programa, lo ejecutamos sobre networks cuyo flujo maximal ya conocemos, y comparamos ese valor (y el corte minimal) con los resultados que devuelve el programa.
En cuanto al funcionamiento en PC's con menos de 256MB de RAM, corrimos el programa en una máquina virtual de esas características, y vimos que no ocurren problemas. Incluso chequeamos el consumo de memoria, y en el peor caso (networks grandes), la memoria utilizada es menos de 8 MB. 

\end{document}
